package com.jzoffer;

public class BalancedTree {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(21);
        TreeNode t3 = new TreeNode(31);
        TreeNode t4 = new TreeNode(41);
        t1.left = t2;
        t1.right = t3;
        t3.left = t4;
        System.out.println(IsBalanced_Solution(t1));
    }

    public static boolean IsBalanced_Solution(TreeNode root){
        if(root == null){
            return true;
        }
        if (Math.abs(height(root.left) - height(root.right)) > 1){
            return false;
        }
        return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
    }

    public static int height(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = height(root.left);
        int right = height(root.right);
        return  1+ ( left > right ? left : right);
    }
}
